In [12]:
import numpy as np
import matplotlib.pyplot as plt
import itertools
import math
In [30]:
def calculate_copeland(node, nodes, edges, directions):
    copeland_score = 0
    for node2 in nodes:
        if node == node2:
            continue
        if node2 > node:
            if directions[edges[(node, node2)]] == "0":
                copeland_score += 1
        elif directions[edges[(node2, node)]] == "1":
            copeland_score += 1
    return copeland_score


def calculate_max_copeland(nodes, edges, directions):
    return max(calculate_copeland(node, nodes, edges, directions) for node in nodes)


def run_se(nodes, edges, directions):
    """Returns Copeland score of winner on the seeding given by nodes
    Edges give indices into directions, and directions is a string consisting of 0s and 1s
    (0 indicates that the first item in the pair wins)
    """
    orig_nodes = nodes
    
    # Run SE
    while len(nodes) > 1:
        next_level = []
        for i in range(0, len(nodes), 2):
            if i + 1 == len(nodes):
                next_level.append(nodes[i])
            else:
                u, v = nodes[i], nodes[i + 1]
                if u > v:
                    u, v = v, u
                if directions[edges[(u, v)]] == "0":
                    next_level.append(u)
                else:
                    next_level.append(v)
        nodes = next_level
    
    return calculate_copeland(nodes[0], orig_nodes, edges, directions)


def simulate_all(n):
    """Returns an np array E[d+(F(T))]/(max_{s in S} d+(s)) for every tournament, T, on n nodes
    """
    nodes = list(range(n))
    edges = {}
    num_edges = 0
    for i in range(len(nodes)):
        for j in range(i + 1, len(nodes)):
            u = nodes[i]
            v = nodes[j]
            edges[(u, v)] = num_edges
            num_edges += 1
    
    res = []
    format_string = f"{{:0{num_edges}b}}"
    for tournament in range(2 ** num_edges):
        directions = format_string.format(tournament)
        num_seedings = 0
        total = 0
        for seeding in itertools.permutations(nodes):
            total += run_se(seeding, edges, directions)
            num_seedings += 1
        expected_winner_score = total / num_seedings
        max_copeland_score = calculate_max_copeland(nodes, edges, directions)
        res.append(expected_winner_score / max_copeland_score)
    return np.array(res)
In [36]:
def theoretical_min(n):
    return math.log2(n) / (n - 2)
In [62]:
def simulate_visual(num_nodes):
    the_min = theoretical_min(num_nodes)
    responses = simulate_all(num_nodes)
    fig, ax = plt.subplots()
    ax.plot(np.sort(responses))
    ax.hlines([the_min, np.mean(responses)], 0, len(responses) - 1, color="red")
    ax.set_title(f"$n = {num_nodes}$")
    print(the_min, np.mean(responses))
    plt.show()
In [63]:
simulate_visual(5)

0.7739760316291208 0.9036458333333335
In [83]:
simulate_visual(6)

0.646240625180289 0.9285481770833334
In [84]:
# simulate_visual(7) (probably takes at least 16 GB, not happening)

---------------------------------------------------------------------------
KeyboardInterrupt                         Traceback (most recent call last)
<ipython-input-84-06645b31d39a> in <module>
----> 1 simulate_visual(7)

<ipython-input-62-a59b6147fa3f> in simulate_visual(num_nodes)
      1 def simulate_visual(num_nodes):
      2     the_min = theoretical_min(num_nodes)
----> 3     responses = simulate_all(num_nodes)
      4     fig, ax = plt.subplots()
      5     ax.plot(np.sort(responses))

<ipython-input-30-a00fe38d3bf4> in simulate_all(n)
     62         total = 0
     63         for seeding in itertools.permutations(nodes):
---> 64             total += run_se(seeding, edges, directions)
     65             num_seedings += 1
     66         expected_winner_score = total / num_seedings

<ipython-input-30-a00fe38d3bf4> in run_se(nodes, edges, directions)
     26     while len(nodes) > 1:
     27         next_level = []
---> 28         for i in range(0, len(nodes), 2):
     29             if i + 1 == len(nodes):
     30                 next_level.append(nodes[i])

KeyboardInterrupt:
In [ ]:
# simulate_visual(8) nope
In [72]:
def simulate_sample(n, n_tournaments):
    """Returns an np array E[d+(F(T))]/(max_{s in S} d+(s)) for n_tournaments tournaments, T, on n nodes
    """
    np.random.seed(0)
    
    nodes = list(range(n))
    edges = {}
    num_edges = 0
    for i in range(len(nodes)):
        for j in range(i + 1, len(nodes)):
            u = nodes[i]
            v = nodes[j]
            edges[(u, v)] = num_edges
            num_edges += 1
    
    res = []
    format_string = f"{{:0{num_edges}b}}"
    for tournament in range(n_tournaments):
        directions = format_string.format(np.random.randint(0, 2 ** num_edges))
        num_seedings = 0
        total = 0
        for seeding in itertools.permutations(nodes):
            total += run_se(seeding, edges, directions)
            num_seedings += 1
        expected_winner_score = total / num_seedings
        max_copeland_score = calculate_max_copeland(nodes, edges, directions)
        res.append(expected_winner_score / max_copeland_score)
    return np.array(res)

def simulate_visual_sample(num_nodes, n_tournaments):
    the_min = theoretical_min(num_nodes)
    responses = simulate_sample(num_nodes, n_tournaments)
    fig, ax = plt.subplots()
    ax.plot(np.sort(responses))
    ax.hlines([the_min, np.mean(responses)], 0, len(responses) - 1, color="red")
    ax.set_title(f"$n = {num_nodes}$")
    print(the_min, np.min(responses), np.mean(responses))
    plt.show()
In [73]:
simulate_visual_sample(5, 2000)

0.7739760316291208 0.7777777777777778 0.9007000000000003
In [74]:
simulate_visual_sample(6, 2000)

0.646240625180289 0.8277777777777777 0.9285333333333333
In [78]:
def simulate_sample_both(n, n_tournaments, n_seedings):
    """Returns an np array E[d+(F(T))]/(max_{s in S} d+(s)) for n_tournaments tournaments, T, on n nodes
    with n_seedings per tournament
    """
    np.random.seed(0)
    
    nodes = list(range(n))
    edges = {}
    num_edges = 0
    for i in range(len(nodes)):
        for j in range(i + 1, len(nodes)):
            u = nodes[i]
            v = nodes[j]
            edges[(u, v)] = num_edges
            num_edges += 1
    
    res = []
    format_string = f"{{:0{num_edges}b}}"
    for tournament in range(n_tournaments):
        directions = format_string.format(np.random.randint(0, 2 ** num_edges))
        num_seedings = 0
        total = 0
        for seeding in range(n_seedings):
            total += run_se(np.random.permutation(nodes), edges, directions)
            num_seedings += 1
        expected_winner_score = total / num_seedings
        max_copeland_score = calculate_max_copeland(nodes, edges, directions)
        res.append(expected_winner_score / max_copeland_score)
    return np.array(res)

def simulate_visual_sample_both(num_nodes, n_tournaments, n_seedings):
    the_min = theoretical_min(num_nodes)
    responses = simulate_sample_both(num_nodes, n_tournaments, n_seedings)
    fig, ax = plt.subplots()
    ax.plot(np.sort(responses))
    ax.hlines([the_min, np.mean(responses)], 0, len(responses) - 1, color="red")
    ax.set_title(f"$n = {num_nodes}$")
    print(the_min, np.min(responses), np.mean(responses))
    plt.show()
In [82]:
for i in range(5, 20):
    simulate_visual_sample_both(i, 2000, 100)

0.7739760316291208 0.7133333333333334 0.9047916666666667

0.646240625180289 0.7925 0.9287245833333334

0.5614709844115209 0.762 0.9199922500000001

0.5 0.8019999999999999 0.9119239166666666

0.45284642877747316 0.7333333333333334 0.847405880952381

0.4152410118609203 0.7157142857142856 0.8682582142857143

0.3843812909596997 0.75625 0.8735383829365079

---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-82-d1bf7bf76091> in <module>
      1 for i in range(5, 20):
----> 2     simulate_visual_sample_both(i, 2000, 100)

<ipython-input-78-b68e46f63116> in simulate_visual_sample_both(num_nodes, n_tournaments, n_seedings)
     31 def simulate_visual_sample_both(num_nodes, n_tournaments, n_seedings):
     32     the_min = theoretical_min(num_nodes)
---> 33     responses = simulate_sample_both(num_nodes, n_tournaments, n_seedings)
     34     fig, ax = plt.subplots()
     35     ax.plot(np.sort(responses))

<ipython-input-78-b68e46f63116> in simulate_sample_both(n, n_tournaments, n_seedings)
     18     format_string = f"{{:0{num_edges}b}}"
     19     for tournament in range(n_tournaments):
---> 20         directions = format_string.format(np.random.randint(0, 2 ** num_edges))
     21         num_seedings = 0
     22         total = 0

mtrand.pyx in numpy.random.mtrand.RandomState.randint()

_bounded_integers.pyx in numpy.random._bounded_integers._rand_int64()

ValueError: high is out of bounds for int64